/**
 * 编写一个程序，通过填充空格来解决数独问题。
 *
 * 数独的解法需 遵循如下规则：
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * 题解：https://labuladong.gitee.io/algo/4/31/109/
 */
class SolveSudoku {
    public void solveSudoku(char[][] board) {
        backtrack(board,0,0);
    }
    public boolean backtrack(char[][] board,int i,int j) {
        if(j==9) {
            //穷举到最后一列就换下一行
            return backtrack(board,i+1,0);
        }
        if(i==9) {
            //穷举到最后一行说明找到一种解法
            return true;
        }
        if(board[i][j]!='.') {
            return backtrack(board,i,j+1);
        }
        for(char ch = '1';ch<='9';ch++) {
            //判断可不可以填入
            if(!isValid(board,i,j,ch)) {
                continue;
            }
            board[i][j]=ch;
            if(backtrack(board,i,j+1)) {
                return true;
            }
            board[i][j]='.';
        }
        return false;
    }
    private boolean isValid(char[][] board,int r,int c,char n) {

        for(int i=0;i<9;i++) {
            //判断行位置
            if(board[r][i]==n) {
                return false;
            }
            //判断列位置
            if(board[i][c]==n) {
                return false;
            }
            //判断3x3位置
            if(board[(r/3)*3+i/3][(c/3)*3+i%3]==n) {
                return false;
            }
        }
        return true;
    }
}